/*
 * @Author: dadadaXU 1413107032@qq.com
 * @Date: 2025-02-19 11:05:06
 * @LastEditors: dadadaXU 1413107032@qq.com
 * @LastEditTime: 2025-02-20 10:43:39
 * @FilePath: \LeetCode\102.二叉树的层序遍历.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
/*
 * @lc app=leetcode.cn id=102 lang=cpp
 *
 * [102] 二叉树的层序遍历
 *
 * 方法1：层序遍历
 * - 区分各层节点：<TreeNode *, int> 标记各个节点的层级
 * - 将数据结构设置在成员函数外会严重影响运行效率 -> 析构 & 函数局部变量
 */

#include <vector>
#include <queue>

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

// @lc code=start

class Solution
{
public:
    std::vector<std::vector<int>> levelOrder(TreeNode *root)
    {
        std::vector<std::vector<int>> result;
        std::vector<int> levelNodes;
        std::queue<std::pair<TreeNode *, int>> treeNodeQ; // 节点 + 层级

        int currentLevel = 0;
        if (root != nullptr)
            treeNodeQ.push({root, currentLevel});

        /* 层序遍历 */
        while (!treeNodeQ.empty())
        {
            auto treeNode = treeNodeQ.front();
            treeNodeQ.pop();

            /* 进入下一层 */
            if (currentLevel < treeNode.second)
            {
                result.emplace_back(levelNodes);
                levelNodes.clear();
                currentLevel++;
            }

            levelNodes.emplace_back(treeNode.first->val);

            if (treeNode.first->left != nullptr)
                treeNodeQ.push({treeNode.first->left, treeNode.second + 1});
            if (treeNode.first->right != nullptr)
                treeNodeQ.push({treeNode.first->right, treeNode.second + 1});
        }
        /* 最后一层 */
        if (!levelNodes.empty())
            result.emplace_back(levelNodes);

        return result;
    }
};
// @lc code=end
